/*
 *归并排序
 */
#include<iostream>
#include<vector>
using namespace std;

void merge(vector<int> &nums,int lo,int mid,int hi)//左闭右闭区间
{
    vector<int> res(nums);
    int le=lo;
    int ri=mid+1;
    for(int i=lo;i!=hi+1;++i)
    {
        if(le>mid)
            res[i]=nums[ri++];
        else if(ri>hi)
            res[i]=nums[le++];
        else if(nums[le]<nums[ri])
            res[i]=nums[le++];
        else 
            res[i]=nums[ri++];
    }
    nums=res;
}


void merge_sort(vector<int> &nums,int lo,int hi)
{
    if(lo>=hi)
        return;
    int mid=(lo+hi)/2;
    merge_sort(nums,lo,mid);
    merge_sort(nums,mid+1,hi);
    if(nums[mid]>nums[mid+1])//这种情况才合并
        merge(nums,lo,mid,hi);
}

int main()
{
    vector<int> nums={1,2,15,0,5,34};
    merge_sort(nums,0,5); 
    for(auto num:nums)
    {
        cout<<num<<" ";
    }
    return 0;
}